package sort;

import tools.RandomArray;

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right){
        if(left < right){
            swap(arr, (int) (left+(Math.random() * (right - left + 1))),right);
            int[] p = partation(arr,left,right);
            quickSort(arr, left,p[0] - 1);
            quickSort(arr,p[1] + 1, right);
        }
    }
    public static int[] partation(int[] arr, int left, int right){
        int less = left - 1;
        int more = right;
        while(left < more){
            if(arr[left] < arr[right]){
                swap(arr,++less,left++);
            }else if(arr[left] > arr[right]){
                swap(arr,--more,left);
            }else{
                left++;
            }
        }
        swap(arr,more,right);
        return new int[]{less + 1, more};
    }
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = RandomArray.generateRandomArray(10, 30);
        quickSort(arr,0, arr.length - 1);
        for(int i : arr)
            System.out.print(i + " ");
    }
}
